﻿//大数乘法
//class Solution
//{
//public:
//    string solve(string s, string t)
//    {
//        if (s.empty())
//        {
//            return t;
//        }
//        if (t.empty())
//        {
//            return s;
//        }
//        if (s == "0" || t == "0")
//        {
//            return "0";
//        }
//        string str(t);
//        string sp(s.size(), '0');
//        sp[s.size() - 1] = '1';
//        while (sp != s)
//        {
//            if (s[s.size() - 1] == '0')
//            {
//                int i = s.size() - 2;
//                while (s[i] == '0')
//                {
//                    s[i] = '9';
//                    i--;
//                }
//                s[i] -= 1;
//                s[s.size() - 1] = '9' + 1;
//            }
//            //str与t加法操作
//            int x = 0; //进位数
//            for (int i = 1; i <= t.size(); i++)
//            {
//                str[str.size() - i] += x + t[t.size() - i] - 48;
//                if (str[str.size() - i] > '9')
//                {
//                    str[str.size() - i] -= 10;
//                    x = 1;
//                }
//                else
//                {
//                    x = 0;
//                }
//            }
//            if (x == 1)
//            {
//                for (int i = str.size() - t.size() - 1; i >= 0; i--)
//                {
//                    if (str[i] + x > '9')
//                    {
//                        str[i] = '0';
//                        x = 1;
//                    }
//                    else
//                    {
//                        str[i] += x;
//                        x = 0;
//                        break;
//                    }
//                }
//                if (x == 1)
//                {
//                    str.insert(str.begin(), '1');
//                }
//            }
//            s[s.size() - 1] -= 1;
//        }
//        return str;
//    }
//};



//岛屿数量
//#include <iostream>
//#include <string>
//#include <map>
//using namespace std;
//
//int main()
//{
//    string str;
//    map<int, string> m;
//    cin >> str;
//    for (int i = 0; i < str.size(); i++)
//    {
//        int count = 0;
//        string s;
//        while (str[i] >= '0' && str[i] <= '9')
//        {
//            count++;
//            s.push_back(str[i]);
//            i++;
//        }
//        if (count)
//        {
//            m[count] = s;
//        }
//    }
//    int max = 0;
//    for (map<int, string>::iterator it = m.begin(); it != m.end(); it++)
//    {
//        if (it->first > max)
//        {
//            max = it->first;
//        }
//    }
//    cout << m[max] << endl;
//    return 0;
//}



//#include <iostream>
//using namespace std;
//
//int main()
//{
//    long long a = 0, b = 0;
//    cin >> a >> b;
//    if (a != 1 && b != 1)
//    {
//        long long m = a > b ? a : b;
//        long long n = a < b ? a : b;
//        while (1)
//        {
//            long long r = m % n;
//            if (r == 0)
//            {
//                break;
//            }
//            m = n;
//            n = r;
//        }
//        cout << a * b / n << endl;
//    }
//    else
//    {
//        if (a == 1)
//        {
//            cout << b << endl;
//        }
//        else
//        {
//            cout << a << endl;
//        }
//    }
//    return 0;
//}


//class Solution {
//public:
//    /**
//     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//     *
//     * max increasing subsequence
//     * @param arr int整型vector the array
//     * @return int整型
//     */
//    int MLS(vector<int>& arr) {
//        int count = 1;
//        sort(arr.begin(), arr.end());
//        vector<int> v(1, arr[0]);
//        for (int i = 1; i < arr.size(); i++)
//        {
//            if (v.back() != arr[i])
//            {
//                v.push_back(arr[i]);
//            }
//        }
//        for (int i = 0; i < v.size(); i++)
//        {
//            int x = 1;
//            while (i != v.size() - 1 && v[i] + 1 == v[i + 1])
//            {
//                x++;
//                i++;
//            }
//            if (x > count)
//            {
//                count = x;
//            }
//        }
//        return count;
//    }
//};